class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left_sum) -> void {
            int d = k - path.size(); // 还要选 d 个数
            if (left_sum < 0 || left_sum > (i * 2 - d + 1) * d / 2)
            {
                return; // 剪枝
            }
            if (d == 0) // 找到一个合法组合
            {
                ans.emplace_back(path);
                return;
            }
            for (int j = i; j >= d; j--) // 枚举的数不能太小，否则后面没有数可以选
            {
                path.push_back(j);
                dfs(j - 1, left_sum - j);
                path.pop_back(); // 恢复现场
            }
        };
        dfs(9, n); // 从 i=9 开始倒着枚举
        return ans;
    }
};